package org.example.myleet.rosalind.sgra;

import org.example.myleet.Utils.JsonUtils;
import org.example.myleet.rosalind.utils.AminoAcidMassReader;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.*;

public class Solution {

    private static final BigDecimal MAX_MASS = BigDecimal.valueOf(200);
    private static final BigDecimal MIN_MASS = BigDecimal.valueOf(50);

    private static final BigDecimal ERROR = BigDecimal.valueOf(0.001);

    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        try (BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)))) {
            List<BigDecimal> weights = new ArrayList<>();
            String line;
            while (null != (line = br.readLine())) {
                line = line.trim();
                if (line.length() < 1) {
                    break;
                }
                weights.add(new BigDecimal(line));
            }
            weights.sort(Comparator.naturalOrder());
            Map<String, BigDecimal> aminoAcidMapMass = AminoAcidMassReader.getAminoAcidMassMap();
//            String[][] dp = new String[weights.size()][weights.size()];
//            for (int i = 0; i < weights.size(); ++i) {
//                for (int j = 0; j < weights.size(); ++j) {
//                    dp[i][j] = findAminoAcid(weights.get(i), weights.get(j), aminoAcidMapMass);
//                }
//            }
            Node root = new Node("", weights.get(0));
            constructSpectrumGraph(weights, aminoAcidMapMass, root, 0);
            List<String> res = new ArrayList<>();
            dfsBackTrack(root, new StringBuilder(), res);
            //找到所有可能形成的序列，排序找出最长的序列
            res.sort((o1, o2) -> o2.length() - o1.length());
            System.out.println(res.get(0));
            System.out.println(res);
//            for (String[] row : dp) {
//                System.out.println(JsonUtils.toJson(row));
//            }
        }
    }

    private static String findAminoAcid(BigDecimal a, BigDecimal b, Map<String, BigDecimal> aminoAcidMapMass) {
        String aa = " ";
        BigDecimal diff = a.subtract(b).abs();
        if (diff.compareTo(MIN_MASS) < 0 || MAX_MASS.compareTo(diff) < 0) {
            return aa;
        }
        for (Map.Entry<String, BigDecimal> entry : aminoAcidMapMass.entrySet()) {
            if (entry.getValue().subtract(diff).abs().compareTo(ERROR) < 0) {
                aa = entry.getKey();
                break;
            }
        }
        return aa;
    }

    //创建质谱质量节点图，针对某个质量读数，在有序的序列上向更大的质量寻找是否存在两个质量相减等于一个氨基酸质量的数值
    //如果找到，则下一个质量作为子节点，并且创建有向边，记录这条边代表的氨基酸
    private static void constructSpectrumGraph(List<BigDecimal> weights, Map<String, BigDecimal> aminoAcidMapMass, Node parent, int i) {
        if (i >= weights.size()) {
            return;
        }
        for (int j = i + 1; j < weights.size(); ++j) {
            BigDecimal diff = parent.weight.subtract(weights.get(j)).abs();
            //数值差范围不能太小也不能太大，否则就忽略
            if (diff.compareTo(MIN_MASS) < 0) {
                continue;
            }
            if (MAX_MASS.compareTo(diff) < 0) {
                break;
            }
            //数值在合理范围内，则尝试计算数值是否为某氨基酸，注意数值是有误差的，这里根据题目数据尝试发现误差小于0.001就算匹配
            String aa = "";
            for (Map.Entry<String, BigDecimal> entry : aminoAcidMapMass.entrySet()) {
                if (entry.getValue().subtract(diff).abs().compareTo(ERROR) < 0) {
                    aa = entry.getKey();
                    break;
                }
            }
            if (aa.length() > 0) {
                //找到一个匹配的氨基酸，创建子节点和边，并DFS递归
                Node child = new Node(aa, weights.get(j));
                parent.children.add(child);
                constructSpectrumGraph(weights, aminoAcidMapMass, child, j);
            }
        }
    }

    //获得了质谱质量节点图之后，只要从根节点开始向叶子节点遍历就可以得到对应的序列，到达一个叶子节点算一个序列，注意回溯
    private static void dfsBackTrack(Node parent, StringBuilder sb, List<String> res) {
        if (parent.children.size() < 1) {
            if (0 < sb.length()) {
                res.add(sb.toString());
            }
            return;
        }
        for (Node child : parent.children) {
            sb.append(child.aa);
            dfsBackTrack(child, sb, res);
            sb.delete(sb.length() - child.aa.length(), sb.length());
        }
    }

    private static class Node {
        List<Node> children;
        /**
         * aa是由parent的weight减去当前的weight对应的氨基酸
         */
        String aa;
        BigDecimal weight;

        public Node(String aa, BigDecimal weight) {
            this.aa = aa;
            this.weight = weight;
            this.children = new ArrayList<>();
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Node{");
            sb.append("aa='").append(aa).append('\'');
            sb.append(", weight=").append(weight);
            sb.append('}');
            return sb.toString();
        }
    }
}
